package leetcode.od;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author pppppp
 * @date 2022/4/14 22:13
 * 描述
 * 编写一个程序，将输入字符串中的字符按如下规则排序。
 *
 * 规则 1 ：英文字母从 A 到 Z 排列，不区分大小写。
 * 如，输入： Type 输出： epTy
 *
 * 规则 2 ：同一个英文字母的大小写同时存在时，按照输入顺序排列。
 * 如，输入： BabA 输出： aABb
 *
 * 规则 3 ：非英文字母的其它字符保持原来的位置。
 * 如，输入： By?e 输出： Be?y
 *
 */
public class HJ26_字符串排序 {
    @Test
    public void T_0(){
      String [] str = {"Type","BabA","By?e","A Famous Saying: Much Ado About Nothing (2012/8)."};
      String [] ans = {"epTy","aABb","Be?y","A aaAAbc dFgghh: iimM nNn oooos Sttuuuy (2012/8)."};
        for (int i = 0; i < str.length; i++) {
            System.out.println(solution(str[i]).equals(ans[i]));
            // System.out.println(solution2(str[i]).equals(ans[i]));
        }
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String s = scanner.nextLine();
            System.out.println(solution2(s));
        }
    }

    /*桶排序*/
    private static String solution(String s) {
        ArrayList<List<Character>> list = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            list.add(new ArrayList<>());
        }
        ArrayList<Integer> spchar = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (!(s.charAt(i) >= 'a' && s.charAt(i) <= 'z' || s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')) {
                spchar.add(i);
            } else {
                int vi = s.charAt(i) >= 'a' ? s.charAt(i) - 'a': s.charAt(i) - 'A';
                list.get(vi).add(s.charAt(i));
            }
        }
        ArrayList<Character> res = new ArrayList<>();
        for (List<Character> characterList : list) {
            res.addAll(characterList);
        }
        for (Integer index : spchar) {
            res.add(index,s.charAt(index));
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (Character re : res) {
            stringBuilder.append(re);
        }
        return String.valueOf(stringBuilder);
    }
        private static String solution2(String s) {
        ArrayList<Character> list = new ArrayList<>();
        ArrayList<Integer> spchar = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if(!(s.charAt(i) >= 'a' && s.charAt(i) <= 'z' || s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') ){
                spchar.add(i);
            }else {
                list.add(s.charAt(i));
            }
        }

        for (int i = 0; i < list.size(); i++) {
            for (int j = i+1; j < list.size(); j++) {
                int vi = list.get(i) >= 'a' ? list.get(i) - 'a': list.get(i) - 'A';
                int vj = list.get(j) >= 'a' ? list.get(j) - 'a': list.get(j) - 'A';
                if(vi > vj){
                    list.add(i,list.get(j));
                    list.remove(j+1);
                }
            }
        }
        for (Integer integer : spchar) {
            list.add(integer,s.charAt(integer));
        }
        StringBuilder sb = new StringBuilder();
        for (Character character : list) {
            sb.append(character);
        }
        return new String(sb);
    }

}
